import java.util.ArrayList;
import java.util.List;

/**
 * @author VernHe
 *
 * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 *
 * 示例:
 *
 * 输入: [1,2,3]
 * 输出:
 * [
 *   [1,2,3],
 *   [1,3,2],
 *   [2,1,3],
 *   [2,3,1],
 *   [3,1,2],
 *   [3,2,1]
 * ]
 *
 */
public class Solution_046 {

    public static void main(String[] args) {
        int[] nums = {1,2,3};
        System.out.println(new Solution_046().permute(nums));
    }

    /**
     * 最原始解法
     */
//    List<List<Integer>> result;
//    List<Integer> selected;
//    public List<List<Integer>> permute(int[] nums) {
//        if (nums.length < 1) {
//            return result;
//        }
//        result = new ArrayList<>();
//        selected = new ArrayList<>(nums.length);
//        select(nums);
//        return result;
//    }
//
//    void select(int[] nums) {
//        // 如果找到一种排列
//        if (selected.size() == nums.length) {
//            // 保存当前的排列顺序
//            List<Integer> way = new ArrayList<>(selected.size());
//            selected.forEach((num) -> {
//                way.add(num);
//            });
//            result.add(way);
//            return;
//        }
//        // 遍历查找
//        int selectedNum;
//        for (int i = 0; i < nums.length; i++) {
//            // 已经选择过
//            if (selected.contains(nums[i])) {
//                continue;
//            }
//            // 还未选择
//            selectedNum = nums[i];
//            selected.add(selectedNum);
//            // 继续选择
//            select(nums);
//            selected.remove(selected.size() - 1);
//        }
//    }

    /**
     * 对剪枝判断进行优化
     */
    List<List<Integer>> result;
    List<Integer> selected;
    boolean[] hasSelected;
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length < 1) {
            return result;
        }
        hasSelected = new boolean[nums.length];
        result = new ArrayList<>();
        selected = new ArrayList<>(nums.length);
        select(nums);
        return result;
    }

    void select(int[] nums) {
        // 如果找到一种排列
        if (selected.size() == nums.length) {
            // 保存当前的排列顺序
            List<Integer> way = new ArrayList<>(selected.size());
            way.addAll(selected);
            result.add(way);
            return;
        }
        // 遍历查找
        int selectedNum;
        for (int i = 0; i < nums.length; i++) {
            // 已经选择过
            if (hasSelected[i]) {
                continue;
            }
            // 还未选择
            selectedNum = nums[i];
            selected.add(selectedNum);
            hasSelected[i] = true;
            // 继续选择
            select(nums);
            hasSelected[i] = false;
            selected.remove(selected.size() - 1);
        }
    }
}
